/*
求字符串t在字符串s中出现了几次，不考虑子串重叠的情况
*/
#include<iostream>
#include<string>
#include<vector>
using namespace std;

/* 解法1 -- 暴力匹配 */
int Count1(string s, string t)
{
	// 统计累计出现次数
	int cnt=0;
	
	// 两字符串长度
	int n=s.size(), m=t.size();
	
	// 指向两字符串的指针
	int i=0, j=0;
	
	// 暴力匹配
	while (i<n && j<m)
	{
		// 比较的两个字符相同时，两指针向后移
		if (s[i]==t[j])
		{
			i++; 
			j++;
		}
		
		// 比较的两个字符不相同时
		else
		{
			// i回退到i原始位置的下一位
			i=i-j+1;	
			
			// j从0开始
			j=0;
		}
		
		// 出现次数增1
		if(j>=m)
		{
			cnt++;
			
			// j从0开始继续
			j=0;	
		}
	}
	
	// 返回出现个数
	return cnt;
}

/* 解法二 -- KMP算法 */
// 求t的next数组
void getnext(string& t,vector<int>& next)
{
	// j遍历t，k记录t[j]之前与t开头相同的字符个数
	int j, k;
	j=0; k=-1;
	
	// 设置next[0]值
	next[0] = k;
	
	// 求t所有位置的next值
	while (j < t.size()-1)
	{
		// k为-1或比较的字符相等时
		if (k==-1 || t[j]==t[k])
		{
			// j、k依次移到下一个字符
			j++; k++;
			
			// 设置next[j]为k
			next[j]=k;
		}
		
		// k回退
		else  k=next[k];
	}
}

int Count2(string s,string t)
{
	// 统计累计出现次数
	int cnt=0;
	
	// 两字符串大小
	int n=s.size(),m=t.size();
	
	// 构建NEXT数组
	vector<int> next(m,-1);
	getnext(t, next);
	
	// 指向两字符串
	int i=0, j=0;
	
	
	while(i < n)
	{
		// 匹配，i和j同时向后移动
		if (j==-1 || s[i]==t[j])
		{
			i++;
			j++;
		}
		
		// 不匹配
		else
			j=next[j]; // j寻找之前匹配的位置
		
		// 成功匹配一次
		if (j>=m)
		{
			cnt++;
			j=0;	 // 匹配成功后t从头开始比较 
		}
 	}
	return cnt;
}

int main()
{
	// 两字符串
	string s="aaaaa";
	string t="aa";
	
	// 打印结果
	printf("解法1\n"); 
	cout << "  " << t << "在" << s << "中出现次数=" << Count1(s,t) << endl;
	printf("解法2\n"); 
	cout << "  " << t << "在" << s << "中出现次数=" << Count2(s,t) << endl;
	return 0;
}
